import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvSource;

/**
 * 二进制字符串相加
 * 题目：给你两个二进制字符串，返回它们的和（用二进制表示）。
 * 输入为 非空 字符串且只包含数字1和0
 * <p>
 * 示例1:
 * 输入: a = "11", b = "1"
 * 输出: "100"
 * <p>
 * 示例2:
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 * <p>
 * 提示：
 * <p>
 * 每个字符串仅由字符 '0' 或 '1' 组成。
 * 1 <= a.length, b.length <= 10^4
 * 字符串如果不是 "0" ，就都不含前导零。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-binary
 *
 * @author godfrey
 * @since 2020-10-13
 */
@DisplayName("二进制字符串相加")
public class AddBinary extends BaseTest {

    @DisplayName("模拟法：时间复杂度O(n)，空间复杂度O(1)")
    @ParameterizedTest
    @CsvSource({"101010,01001", "1010101010,01010101"})
    void addBinary(String a, String b) {
        StringBuilder result = new StringBuilder();
        int ai = a.length() - 1, bi = b.length() - 1;
        //进位
        int carry = 0;
        while (ai >= 0 || bi >= 0 || carry > 0) {
            int valueA = ai < 0 ? 0 : a.charAt(ai--) - '0';
            int valueB = bi < 0 ? 0 : b.charAt(bi--) - '0';
            int sum = valueA + valueB + carry;
            carry = sum / 2;
            result.append(sum % 2);
        }
        System.out.println(result.reverse().toString());
    }

    @DisplayName("先将 a 和 b 转化成十进制数，求和后再转化为二进制数：时间复杂度O(m+n)，空间复杂度O(1)")
    @ParameterizedTest
    @CsvSource({"101010,01001", "1010101010,01010101"})
    void addBinary2(String a, String b) {
        System.out.println(Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2)));

    }
}